#include "base.h"

class Solution
{
public:
    bool isValid(string s)
    {
        string a;
        a.reserve(s.size() / 2);
        int i = 0;
        while (i < s.size())
        {
            if (s.at(i) == '{' || s.at(i) == '[' || s.at(i) == '(')
            {
                a.push_back(s.at(i));
            }
            else if (s.at(i) == '}' && !a.empty() && a.back() == '{')
            {
                a.pop_back();
            }
            else if (s.at(i) == ']' && !a.empty() && a.back() == '[')
            {
                a.pop_back();
            }
            else if (s.at(i) == ')' && !a.empty() && a.back() == '(')
            {
                a.pop_back();
            }
            else
            {
                return false;
            }

            i++;
        }

        return a.size() == 0;
    }
};

int main()
{
    Solution().isValid("))}}]]{[([}}[}[(([[]]([}(}}[[[]{){[)");
    return 0;
}